package com.tju.ffmpeg

import kotlinx.coroutines.delay
import org.junit.Test

import org.junit.Assert.*
import java.lang.Exception
import java.util.*
import java.util.concurrent.locks.ReentrantLock

/**
 * Example local unit test, which will execute on the development machine (host).
 *
 * See [testing documentation](http://d.android.com/tools/testing).
 */
class ExampleUnitTest {



    @Test
    fun addition_isCorrect() {
        val pq: PriorityQueue<ListNode> = PriorityQueue<ListNode>(kotlin.Comparator { o1, o2 ->
            o1.`val`-o2.`val`
        })
        pq.add(ListNode(0))
    }

    class TreeNode(var `val`: Int) { var left: TreeNode? = null; var right: TreeNode? = null }
    class ListNode(var `val`: Int) { var next: ListNode? = null }

    fun permutation(s: String): Array<String> {
        if(s.length==1) return arrayOf(s)
        val charArray = s.toCharArray()
        sort(charArray, 0, s.length-1)
        val str = String(charArray)
        val result: MutableList<String> = mutableListOf()
        val visited: BooleanArray = BooleanArray(s.length){false}
        dfs(str, result, mutableListOf(), visited)
        val a = 1
        a.toDouble()
        return result.toTypedArray()

        val arr: Array<MutableList<Char>> = Array(3){ mutableListOf() }
    }

    fun dfs(s: String,
            result: MutableList<String>,
            trace: MutableList<Char>,
            visited: BooleanArray) {
        if(trace.size==s.length) {
            result.add(String(trace.toCharArray()))
            return
        }
        for(i in s.indices) {
            if(visited[i]) continue
            if(i>0 && !visited[i-1] && s[i-1]==s[i]) continue
            trace.add(s[i])
            visited[i] = true
            dfs(s, result, trace, visited)
            visited[i] = false
            trace.removeAt(trace.size-1)
        }
    }

    fun swap(s: CharArray, l: Int, r: Int) {
        val t = s[l]
        s[l] = s[r]
        s[r] = t
    }

    fun sort(s: CharArray, start: Int, end: Int) {
        if(start>=end) return
        val mid = premutate(s, start, end)
        sort(s, start, mid-1)
        sort(s, mid+1, end)
    }

    fun premutate(s: CharArray, start: Int, end: Int): Int {
        val rand = (start..end).random()
        swap(s, rand, end)
        var l = start
        var r = end-1
        while(l<=r) {
            while(l<=r && s[l]-'a'<s[end]-'a') l++
            while(l<=r && s[r]-'a'>s[end]-'a') r--
            if(l>=r) break
            swap(s, l++, r--)
        }
        swap(s, l, end)
        return l
    }

}
